package com.java.comprehensive.arithmetic.sort;

import java.util.Arrays;

public class QuickSort {

	public static void main(String[] args) {
		int[] nums = {4, 5, 8, 1, 34, 8679, 234};
		QuickSort quickSort = new QuickSort();
		quickSort.quickSort(nums, 0, nums.length - 1);
		System.out.println(Arrays.toString(nums));
	}

	private void quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int partitionIndex = partition(arr, left, right);
			quickSort(arr, left, partitionIndex - 1);
			quickSort(arr, partitionIndex + 1, right);
		}
	}

	private int partition(int[] arr, int left, int right) {
		// 设定基准值（pivot）
		int pivot = left;
		int index = pivot + 1;
		for (int i = index; i <= right; i++) {
			if (arr[i] < arr[pivot]) {
				swap(arr, i, index);
				index++;
			}
		}
		swap(arr, pivot, index - 1);
		return index - 1;
	}

	private void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}